int mySqrt(int x) {
    int left = 0, right = x;
    int ans = -1;
    while (left <= right) {
        int k = left + (right - left) / 2;
        if ((long)k * k <= x) {
            ans = k;
            left = k + 1;
        } else {
            right = k - 1;
        }
    }
    return ans;
}